Welcome to the lecture Secure Multi-Party Computation.

My name is Dominik Schröder and we are now at lecture number nine.

So let me briefly recall what you've seen in the previous lecture.

So topic-wise we are of course still in the area of malicious secure-to-party computation.

So what we've seen in the past in the previous lectures is that YOW in general, the YOW Scabble

Circuit is not secure in this setting.

So whenever we have malicious parties then we can easily break the underlying functionality

and break the security notion.

So in the past lecture we started following the cut and choose approach.

And cut and choose essentially, I mean it's probably well known from your childhood, comes

from the idea of having a cake.

So there are several parties that would like to have a piece of cake and how can we distribute

these pieces fairly.

And the basic idea is that there is one party cutting the cake and there is a second party

that actually chooses the cake.

So it's clear that if the first party cut the cake in an unfair manner and since this

party is not allowed to choose, the second party who is allowed to choose will essentially

just pick the biggest piece, like that one.

And therefore the best strategy for the one cutting the cake to make sure that the other

party does not receive more is by choosing or by cutting the cake in such a way that

all of the pieces are at the same size, so are of equivalent size.

So in the concrete case of the ausgabelt circuit this in particular meant that we have different

instantiations of a circuit that we wish to compute and then essentially one party asks

to open a subset of these circuits and this is essentially some checking circuits to see

whether they were honestly generated and afterwards we will evaluate the remaining circuits and

take the majority functionality.

There are of course different approaches how to construct these things.

Another approach could be that if we have just some circuit here it doesn't really matter

how the circuit looks like, but the problem is we would like to enforce honest behavior

and of course the question is how can we actually do this?

And of course one approach could be that we are generating certain zero-knowledge proofs,

essentially zero-knowledge proof proving that the inputs were, that we have generated

an honest randomness and that with respect to the randomness the garbling was correct

and so on and so forth and this we would need to do for all of the gates.

Of course this is extremely expensive and therefore we follow the cut and choose approach.

So in this lecture we are continuing this path, so we will in particular finish Yaw's

cut and choose protocol.

In general I would like to stress at this point that this is, I mean you can see this

more as a feasibility result and not as the best thing that we know.

So if you are interested in looking for a more efficient solution, really you can see

this more as a feasibility result, then I encourage you to go on the ePrint server and

this is essentially the publication server of the International Association of Cryptologic

Research, ISCR, this is essentially where all cryptographers are members and here if

you just search therefore malicious security then you will see many many different approaches

that are significantly more efficient than what we are discussing here in this class.

Nevertheless I think the cut and choose approach is elegant by its fundamental design and also

it also demonstrates nicely how much additional work needs to be done in order to get it malicious

security.

So thank you for your attention and the next part of the video was given by me in the previous

lecture.